package binarysearch;

import org.junit.Test;

/**
 * @Description 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * @Author Firenut
 * @Date 2023-01-21 22:01
 */
public class T53II_missingNumber {
    @Test
    public void test() {
        int[] nums = {0, 1, 3, 4, 5};
        missingNumber(nums);
    }

    // 本题的数字起始是从0开始的n-1个数,所以可以利用索引下标进行参照
    // 对应 nums[m]!=mid的情况，应该让j-1,因为 左子数组的末位元素一定在[i,m-1],但右子数组的首位可能在m处，不过没有关系
    // 虽然j-1,可能偏离了右子数组首位,但只要最后 i,j指向左子数组的末尾元素,那么最后一次循环i+1,就能找到丢失数字了
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] != mid) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return i;
    }
}
